package com.tucc.hello.leetcode.no1_400.no1_200.no41_60.no51;

import java.util.ArrayList;
import java.util.List;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        List<List<String>> result = solution.solveNQueens(9);
        System.out.println(result);
        System.out.println(result.size());
    }

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        if (n > 0) {
            for (int i = 0; i < n; i++) {
                template += ".";
            }
            solveNQueens(0, n, new ArrayList<>(), result);
        }
        return result;
    }

    public String template = "";

    public static final char QUEEN = 'Q';

    public void solveNQueens(int cur, int n, List<String> list, List<List<String>> result) {
        if (list.size() == n) {
            List<String> copy = new ArrayList<>(list);
            result.add(copy);
        } else {
            for (int i = 0; i < n; i++) {
                boolean ok = true;
                for (int j = 0; j < cur; j++) {
                    if (list.get(j).charAt(i) == QUEEN) {
                        ok = false;
                        break;
                    }
                    int d = cur - j;
                    if (i - (cur - j) >= 0) {
                        if (list.get(j).charAt(i - cur + j) == QUEEN) {
                            ok = false;
                            break;
                        }
                    }
                    if (i + cur - j < n) {
                        if (list.get(j).charAt(i + cur - j) == QUEEN) {
                            ok = false;
                            break;
                        }
                    }
                }
                if (ok) {
                    String string = template.substring(0, i) + QUEEN + (i < n - 1 ? template.substring(i + 1) : "");
                    list.add(string);
                    solveNQueens(cur + 1, n, list, result);
                    list.remove(list.size() - 1);
                }
            }
        }

    }

}
